package review.Day_0427;

/**
 * @author zxc
 * @date 2023/04/27 16:13
 **/

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 题目 ：最长的字符串链
 * 题目详述 ：
 * 给出一个单词数组words，其中每个单词都由小写英文字母组成。
 * 如果我们可以不改变其他字符的顺序，在 wordA的任何地方添加 恰好一个 字母使其变成wordB，那么我们认为wordA是wordB的 前身 。
 * 例如，"abc"是"abac"的 前身，而"cba"不是"bcad"的 前身
 * 词链是单词[word_1, word_2, ..., word_k]组成的序列，k >= 1，其中word1是word2的前身，word2是word3的前身，依此类推。
 * 一个单词通常是 k == 1 的 单词链。
 * 从给定单词列表 words 中选择单词组成词链，返回 词链的最长可能长度 。
 *
 * 提示：
 * 1 <= words.length <= 1000
 * 1 <= words[i].length <= 16
 * words[i] 仅由小写英文字母组成。
 *
 */
public class LongestStrChain {
    /**
     * 动态规划 ：
     * 即，假设当前字符串的最长字符串S链长度为l,则需要遍历当前字符串缺少一个字符后所有可能字符串t，l = max(t) + 1;
     * ===》
     * （1）对于该字符串数组words，根据各个字符串的长度进行排序;
     *  由于字符串链中各个字符串的长度必然是递增的，所以首先遍历words数组中较短字符串word，获取当前单词的字符串链长度;
     * （2）遍历该字符串数组words，获取当前字符串移其中某个字符后，所构成新字符串的最长字符串链maxLength;
     *
     * @param words
     * @return
     */
    public int longestStrChain(String[] words) {
        Map<String , Integer> map = new HashMap<>();
        // 1.使得该words字符串数组，按照字符串长度，从小到大进行排序;
        Arrays.sort(words , (a , b) -> a.length() - b.length());
        int maxLength = 0;
        // 2.遍历words数组中所有的字符串word;
        for (String word : words) {
            // （1）将当前单词加入到map集合中,用来记录当前单词最长的字符串链;
            map.put(word , 1);
            int len = word.length();
            // （2）将当前字符串word移除其中某个字符后，所形成的新字符串;
            for(int i = 0 ; i < len ; i++){
                String str = word.substring(0 , i) + word.substring(i + 1);
                // （3）判断当前字符串str是否存在于map集合中：
                // 若是存在于map集合中，就将当前字符串word的最长字符串链
                // ===》 修改为 (字符串str的最长字符串链 + 1)和 （字符串word的最长字符串链）中的最大值;
                if(map.containsKey(str)){
                    map.put(word , Math.max(map.get(word),map.get(str) + 1));
                }
            }
            maxLength = Math.max(maxLength , map.get(word));
        }
        return maxLength;
    }
}
